import java.util.Arrays;

public class Sort {

    /**
     * 直接插入排序
     *
     * 时间复杂度：
     * 最坏情况下：O(n^2) 5 4 3 2 1
     * 最好情况下：O(n) 1 2 3 4 5
     * 空间复杂度：O(1)
     * 应用场景： 当数据趋于有序的情况下 直接插入排序效率会变高
     * @param arr
     */
    public static void InsertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i - 1;
            for (; j >= 0 ; j--) {
                if(arr[j] > tmp) {
                    arr[j+1] = arr[j];
                }else {
                    //arr[j+1] = tmp;
                    break;
                }
            }
            //走到这 j 的值为 -1；
            arr[j+1] = tmp;//最前面的值也大于 tmp，tmp要插入到 j+1 位置
        }
    }


    public void bubbleSort(int[] array) {

        for (int i = 0; i < array.length-1; i++) {
            boolean flg = true;
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j] > array[j+1]) {
                    swap(array,j,j+1);
                    flg = false;
                }
            }
            if(flg) {
                break;
            }
        }
    }
    private void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    /**
     * Hoare法快排
     * 时间复杂度：
     * 空间复杂度：
     * 稳定性：
     */

    public void quickSort(int[] array) {
        int par = quick(array,0,array.length-1);
        quick(array,0,par-1);
        quick(array,par+1,array.length-1);
    }

    public int quick(int[] array,int left,int right) {
        int i = left;
        int pivot = array[left];
        while(left < right) {
                while (right > left && array[right] >= pivot) {
                    right--;
                }
                while (right > left && left <= array.length - 1 && array[left] <= pivot) {
                    left++;
                }
                swap(array, left, right);
        }
        swap(array, i, left);
        return left;
    }


    /**
     * 挖坑法快排
     *
     */
    public int quick2(int[] array,int left,int right) {
        int pivot = array[left];
        while(left < right) {
            while (right > left && array[right] >= pivot) {
                right--;
            }
            array[left] = array[right];
            while (right > left && left <= array.length - 1 && array[left] <= pivot) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = pivot;
        return left;
    }
    public void quickSort2(int[] array) {
        int par = quick2(array,0,array.length-1);
        quick2(array,0,par-1);
        quick2(array,par+1,array.length-1);
    }

    /**
     * 前后指针法快排
     */

    public int partition(int[] array,int left,int right) {
        return 0;
    }

    /**
     * 优化：三数取中法 快排
     */

    public int quick3(int[] array,int left,int right) {
        int i = left;
        int pivot = 0;
        //找中值 的 下标，将中值 与 left 下标进行交换
        int ret = midThreeNum(array,left,right);
        swap(array,ret,left);
        pivot = array[left];

        while(left < right) {
            while (right > left && array[right] >= pivot) {
                right--;
            }
            while (right > left && left <= array.length - 1 && array[left] <= pivot) {
                left++;
            }
            swap(array, left, right);
        }
        swap(array, i, left);

        return left;
    }
    private int midThreeNum(int[] array,int left,int right) {
        int mid = (left + right) / 2;
        int ret = 0;
        if(array[left] > array[right]) {
            if(array[mid] > array[left]) {
                return left;
            }else if(array[mid] < array[right]){
                return right;
            }else {
                return mid;
            }
        }else {
            if(array[mid] > array[right]) {
                return right;
            }else if(array[mid] < array[left]){
                return left;
            }else {
                return mid;
            }
        }
    }

    public void quickSort3(int[] array) {
        int par = quick3(array,0,array.length-1);
        quick3(array,0,par-1);
        quick3(array,par+1,array.length-1);
    }

    public int quick4(int[] array,int left,int right) {
        int i = left;
        int pivot = array[left];
        while(left < right) {
            if(right - left + 1 == 4) {
                InsertSort2(array,left,right);
                break;
            }
            while (right > left && array[right] >= pivot) {
                right--;
            }
            while (right > left && left <= array.length - 1 && array[left] <= pivot) {
                left++;
            }
            swap(array, left, right);
        }
        swap(array, i, left);
        return left;
    }

    public static void InsertSort2(int[] arr,int left,int right) {
        for (int i = left + 1; i <= right; i++) {
            int tmp = arr[i];
            int j = i - 1;
            for (; j >= left ; j--) {
                if(arr[j] > tmp) {
                    arr[j+1] = arr[j];
                }else {
                    //arr[j+1] = tmp;
                    break;
                }
            }
            //走到这 j 的值为 -1；
            arr[j+1] = tmp;//最前面的值也大于 tmp，tmp要插入到 j+1 位置
        }
    }
    public void quickSort4(int[] array) {
        int par = quick4(array,0,array.length-1);
        quick4(array,0,par-1);
        quick4(array,par+1,array.length-1);
    }
}